package com.leetcode.algorithm.y22.m07.w4;

/**
 * 75. 颜色分类
 * 
 * https://leetcode.cn/problems/sort-colors/
 * 
 * @author jie.deng
 *
 */
class Question0075Solution01 {

	public void sortColors(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		// 交换蓝色和红色，是所有的红色都在蓝色的前面
		while (left < right) {
			while (left < right && nums[left] != 2) {
				left++;
			}
			while (left < right && nums[right] != 0) {
				right--;
			}
			if (left < right) {
				int tmp = nums[left];
				nums[left] = nums[right];
				nums[right] = tmp;
			}
			left++;
			right--;
		}

		left = 0;
		right = nums.length - 1;
		// 交换白色和红色，是所有的红色都在白色的前面
		while (left < right) {
			while (left < right && nums[left] != 1) {
				left++;
			}
			while (left < right && nums[right] != 0) {
				right--;
			}
			if (left < right) {
				int tmp = nums[left];
				nums[left] = nums[right];
				nums[right] = tmp;
			}
			left++;
			right--;
		}

		left = 0;
		right = nums.length - 1;
		// 交换蓝色和白色，是所有的白色都在蓝色的前面
		while (left < right) {
			while (left < right && nums[left] != 2) {
				left++;
			}
			while (left < right && nums[right] != 1) {
				right--;
			}
			if (left < right) {
				int tmp = nums[left];
				nums[left] = nums[right];
				nums[right] = tmp;
			}
			left++;
			right--;
		}
	}

}